Last Day Where You Can Still Cross

Try to solve the Last Day Where You Can Still Cross problem.

We'll cover the following

Statement#

You are given two integers, rows and cols, which represent the number of rows and columns in a 1-based binary matrix. In this matrix, each 00 represents land, and each 11 represents water.

Initially, on day 0, the whole matrix will just be all 0s, that is, all land. With each passing day, one of the cells of this matrix will get flooded and, therefore, will change to water, that is, from 00 to 11. This continues until the entire matrix is flooded. You are given a 1-based array, water_cells, that records which cell will be flooded on each day. Each element water_cells[i]=[ri,ci]water\_cells[i] = [r_{i},c_{i}] indicates the cell present at the rith{r_{i}}^{th} row and cith{c_{i}}^{th} column of the matrix that will change from land to water on the ithi^{th} day.

We can cross any cell of the matrix as long as it’s land. Once it changes to water, we can’t cross it. To cross any cell, we can only move in one of the four cardinal directions. Given the number of rows and columns of a 1-based binary matrix and a 1-based array, water_cells, you are required to find the last day where you can still cross the matrix, from top to bottom, by walking over the land cells only.

Note: You can start from any cell in the top row, and you need to be able to reach just one cell in the bottom row for it to count as a crossing.

Constraints:

  • 2≤2 \leq rows,, cols ≤2×104\leq 2 \times 10^4
  • 4≤4 \leq rows ×\times cols ≤2×104\leq 2 \times 10^4
  • water_cells.length ==== rows ×\times cols
  • 1≤ri≤1 \leq r_{i} \leq rows
  • 1≤ci≤1 \leq c_{i} \leq cols
  • All values of water_cells are unique.

Examples#

Created with Fabric.js 3.6.6 0 0 0 0 0 0 0 0 0 Sample example 1

1 of 6

Created with Fabric.js 3.6.6 0 1 0 0 0 0 0 0 0 Sample example 1

2 of 6

Created with Fabric.js 3.6.6 0 1 0 1 0 0 0 0 0 Sample example 1

3 of 6

Created with Fabric.js 3.6.6 0 1 0 1 0 0 0 0 1 Sample example 1

4 of 6

Created with Fabric.js 3.6.6 0 1 0 1 1 0 0 0 1 Sample example 1

5 of 6

Created with Fabric.js 3.6.6 1 1 1 0 1 0 0 0 1 1 1 1 Sample example 2

6 of 6

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Last Day Where You Can Still Cross

4

What will be the last day where we can still cross the matrix, from top to bottom, if the following values are given as input?

rows=2rows = 2

cols=4cols = 4

water_cells=[ [1,2], [1,4], [2,1], [1,1], [2,4], [1,3], [2,3], [2,2] ]water\_cells = [~[1, 2], ~[1, 4], ~[2, 1], ~[1, 1], ~[2, 4], ~[1, 3], ~[2, 3], ~[2, 2]~]

Your Answer
A)

5

Explanation

On the 1st day, cell [1, 2] will be filled with water, and we can move from top to the bottom row. On the 2nd day, cell [1, 4] will be filled with water, and we can move from top to the bottom row. On the 3rd, 4th, and 5th days, cells [2, 1], [1, 1], and [2, 4] will be filled and we can still move from top to the bottom row. However, on the 6th day, cell [1, 3] will be filled with water and it is not possible to move from top to the bottom row. Therefore, 5 was the last day where we could still cross.

B)

6

C)

7

D)

8

Question 4 of 44 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize a variable days to keep track of the number of days starting with 00 and a matrix of dimensions, rows ×\times cols, containing all 00s in the start (all land on day 00).

Start filling the matrix with water cells, as per the given water_cells array.

Each time a cell is flooded, check if it can connect with any existing water cells.

After connecting the recently added water cell to the existing water cells, check if we get a single connected component of water cells from the leftmost to the rightmost side of the matrix.

If there exists a series of connected water cells, we’ll stop here and return the current value of the days variable as the final output.

Otherwise, we can still cross the matrix from top to bottom. Therefore, increment the value of days and repeat the process for the next cell to be flooded.

Try it yourself#

Implement your solution in main.py in the following coding playground. You’ll need the provided supporting code to implement your solution.

Python
main.py
union_find.py
Powered by AI
Input #1
Input #2
Input #3
Last Day Where You Can Still Cross

Solution: Longest Consecutive Sequence

Solution: Last Day Where You Can Still Cross